Definition

Let ℳ={0,1}n\mathcal{M} = \{0,1\}^n, 𝒦={0,1}n\mathcal{K} = \{0,1\}^n, 𝒞={0,1}n\mathcal{C} = \{0,1\}^n,

Enc𝐊⁡(m)=m⊕︎kDec𝐊⁡(m)=c⊕︎k \begin{aligned} \operatorname{Enc}_\mathbf{K}(m) & = m \oplus k \\ \operatorname{Dec}_\mathbf{K}(m) & = c \oplus k \end{aligned}

where ⊕︎\oplus denotes bitwise XOR

Proposition

  1. A one-time pad (OTP) is a perfectly secret encryption scheme (correctness).
    $Dec𝐊⁡(Enc𝐊⁡(m))=(m⊕︎k)⊕︎k=m⊕︎(k⊕︎k)=m⊕︎0n=m\operatorname{Dec}_\mathbf{K}(\operatorname{Enc}_\mathbf{K}(m)) = (m \oplus k) \oplus k = m \oplus (k \oplus k) = m \oplus 0^n = m$
  2. OTP is perfectly secure by previous theorem suffices to show that OTP is perfectly indistinguishable.

References

  1. Barak, Boaz. An Intensive Introduction to Cryptography, 2021, p. 58. https://intensecrypto.org/public/lec_01_introduction.html
  2. Vernam, 1917
  3. Shannon, 1949
  4. https://github.com/cpeikert/TheoryOfCryptography/blob/master/lec01 - Overview and Perfect Secrecy.pdf